/*! \file RBTree.h
 *	\brief <write description for RBTree.h>
 *
 *	created:	2010/08/27
 *	created:	27:8:2010   16:47
 *	filename: 	C:\src\tactics-engine\libs\core\RBTree.h
 *	file path:	C:\src\tactics-engine\libs\core
 *	file base:	RBTree
 *	file ext:	h
 *	author:		Vitalii Trubchaninov
 *				venngraydog@gmail.com
 */

#ifndef _core_RBTREE_H_
#define _core_RBTREE_H_

#pragma once

#include <core/pair.h>

#include "impl/RBTreeNode.h"
#include "impl/RBTreeIterator.h"

namespace tt{
namespace core{

template<typename Key, typename Data>
class RBTree
{
public:
	typedef Pair<Key, Data> value_type;
	typedef impl::RBTreeIterator<value_type> iterator;

public:
	RBTree();
	~RBTree();

	iterator insert(const value_type&);

	iterator begin();
	iterator end();

	bool sanityCheck() const;

private:
	typedef impl::RBTreeNode<value_type> Node;

private:
	void rotateLeft(Node*);
	void rotateRight(Node*);
	void correctionInsert(Node*);

private:
	Node* m_root;
};

} //namespace core
} //namespace tt
#include "RBTree.inl"

#endif //_core_RBTREE_H_